package newcoder_exp.justPractise;
import tree.*;
import java.util.*;
/* 
    重建二叉树
*/
public class NC12 {
    
    public class Solution {
        int[] pre, in;
        Map<Integer, Integer> map = new HashMap<>();
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
            if (pre.length != in.length) return null;
            this.pre = pre;
            this.in = in;
            for (int i = 0; i < in.length; i++) {
                map.put(in[i], i);
            }
            return pre(0, 0, in.length - 1);
        }

        public TreeNode pre(int left, int r, int right) {
            if (left > right) return null;
            TreeNode root = new TreeNode(pre[r]);
            int m = map.get(pre[r]);
            int left_len = m - left;
            root.left = pre(left, r + 1, m - 1);
            root.right = pre(m + 1, r + left_len + 1, right);
            return root;
         }
    }
}
